package 牛客.字符串;

/*
题目描述
    给定两个字符串str1和str2,输出两个字符串的最长公共子串
    题目保证str1和str2的最长公共子串存在且唯一。
    示例1
    输入      "1AB2345CD","12345EF"
    返回值    "2345"
 */

public class 最长公共子串 {
    public String LCS (String str1, String str2) {
        // write code here
        int m = str1.length() - 1;
        int n = str2.length() - 1;
        int maxLen = 0, maxIndex = 0;
        int[][] record = new int[m + 1][n + 1];  //二维矩阵记录公共子串位置
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (chars1[i] == chars2[j])
                    if(i == 0 || j == 0)
                        record[i][j] = 1;
                    else
                        record[i][j] = record[i - 1][j - 1] + 1;   //边记录子串边记录数量
                else
                    record[i][j] = 0;
                if(record[i][j] > maxLen){
                    maxLen = record[i][j];
                    maxIndex = i;   //记录当前的i值，方便取子串
                }
            }
        }
        return str1.substring(maxIndex - maxLen + 1, maxIndex + 1);
    }

    public static void main(String[] args) {
        最长公共子串 obj = new 最长公共子串();
        String str1 = "22222";
        String str2 = "22222";
        String lcs = obj.LCS(str1, str2);
        System.out.println(lcs);
    }

}
